P14582 [LNCPC 2025] 被抠的键盘 题解

本文迁移自洛谷原文。

首先发现 是一定没有被抠掉的。如果没有其他别的数字，那么只有 显然是无法得到 的正整数倍数，输出 。

考虑将 除去其所有 因子得到 ，那么 与 互质。由欧拉定理得，，即 个 是 的倍数。再考虑把 补为 的过程，即乘上很多 和 ，只需要在我们的构造后面添上足够多的 即可。

现在我们得到了仅用 就能构造的方案，显然把 换为任意非 数字均成立。由于 ，所以不能直接计算 。我们预处理到 ，然后由 得，可以输出 个相同的任意没被抠掉的数字，最后输出 个 即可，仅需两步。